Aminet 7/Aminet 7 - August 1995.iso/Aminet/docs/misc/ConcNews.lha/news/general.programming/comp.programming_1247_000009.msg

Text File | 1994-11-27 | 4.6 KB | 189 lines

Path: dd.chalmers.se!news.chalmers.se!sunic!EU.net!howland.reston.ans.net!sol.ctr.columbia.edu!news.unomaha.edu!crcnis1.unl.edu!manager
From: [e-mail] (Mike Gleason)
Newsgroups: comp.programming
Subject: Re: Algorithm for finding all possible combinations
Date: 30 Jan 1994 22:57:43 GMT
Organization: NCEMRSoft
Lines: 176
Distribution: world
Message-ID: <2ihe18$[e-mail]>
References: <2ighh8$[e-mail]> <[e-mail]>
NNTP-Posting-Host: cse.unl.edu

[e-mail] (Remo Williams) writes:

|>    I have three chunks of a data, named a, b and c. I need to
|>    process them in every possible order. So I need to organize
|>    them like this:
|>        a b c
|>        a c b
|>        b a c
|>        b c a
|>        c a b
|>        c b a

|Pseduocode:    z:=c
|        for x:= a to c do
|            for y:= b to c do
|            if (x<y) and (y<z) do
|            write (x,y,z)
|            write (z,y,z)

That's swell, but I believe the original poster wanted something for
the general case.

Here's a chunk of code I wrote last year for this purpose.  This is
copyrighted code, but I don't mind what you use it for as long as
you don't use it as your homework assignment:


/* WeakPermDriver.c
 * Copyright 1993 by Mike Gleason.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define DONE                (1)
#define NOT_DONE            (0)
#define DEFAULT_N            (4)
#define MAXPERMSIZE            (32)

typedef int SetElement;
typedef SetElement Permutation[MAXPERMSIZE];

static void PermToCycle(Permutation p, int permSize, char *cycle)
{
    int i, j;
    Permutation used;
    SetElement x, y, cstart;
    int ncycles = 0;

    for (i=0; i<permSize; i++)
        used[i] = 0;

    *cycle++ = '(';
    x = 1;
    used[x-1] = 1;
    cstart = x;
    *cycle++ = (char)(x + '0');

    for (;;) {
        y = p[x-1];
        if (y == cstart) {
            /* End cycle. */
            /* First get rid of any 1-cycles. */
            if (cycle[-2] == '(')
                cycle -= 2;
            else {
                *cycle++ = ')';
                ++ncycles;    /* Count 2-cycles, and larger. */
            }
            x = -1;
            for (j=0; j<permSize; j++)
                if (used[j] == 0) {
                    x = j + 1;
                    cstart = x;
                    used[j] = 1;
                    *cycle++ = '(';
                    *cycle++ = (char)(x + '0');
                    break;
                }
            if (x < 0)
                break;
        } else {
            *cycle++ = (char)(y + '0');
            used[y - 1] = 1;
            x = y;
        }
    }
    if (ncycles == 0)
        *cycle++ = '1';        /* Must be identity cycles. */
    *cycle = 0;
}    /* PermToCycle */

static void PrintPerm(Permutation p, int permSize, int permNum)
{
    int i;
    char cy[128];

    printf("%3d: ", permNum);
    PermToCycle(p, permSize, cy);
    for (i=0; i<permSize; i++)
        printf("%d%c", p[i], (i == permSize - 1) ? ' ' : '-');
    printf(" = %s\n", cy);
}    /* PrintPerm */



static int NextPerm(Permutation p, int permSize)
{
    int i;

    /* First find where in the permutation the "largest" element is. */
    for (i=0; p[i] != permSize; ) ++i;

    /* Check to see if that element is in the first position. */
    if (i==0) {
        /* If this element is in the first position, and the size of
         * the (sub)permutation is only 1 element, there is no next
         * permutation, so say we're finished.  We'll get to this point
         * if the permutation we were asked to "next" was in descending
         * order, and that one is the last one, therefore there is no
         * next permutation.
         */
        if (permSize==1)
            return DONE;

        /* Otherwise, shift all the other elements "back" one slot. */
        memmove(p, p+1, (permSize - 1) * sizeof(SetElement));

        /* Recursively call myself to work on a smaller sub-permutation. */
        if (NextPerm(p, permSize - 1) == DONE)
            return DONE;

        /* Now stick the "largest" element in the last position. */
        p[permSize - 1] = (SetElement) permSize;
    } else {
        p[i] = p[i-1];
        p[i-1] = permSize;
    }
    return (NOT_DONE);
}    /* NextPerm */



void main(int argc, char *argv[])
{
    int n = DEFAULT_N;    /* Number of elements in the set to permute. */
    int permNum = 0;    /* Not the rank, since they're not computed
                         * in ascending order.
                         */
    Permutation perm;    /* The set of elements. */
    int i;

    /* Get the 'n' from the command line, if you specified one. */
    if (argc > 1) {
        i = atoi(argv[1]);
        if ((i > 1) && (i <= MAXPERMSIZE))
            n = i;
    }

    /* Initialize the first permutation. */
    for (i=0; i<n; i++)
        perm[i] = i+1;

    /* Loop until we've found them all. */
    do {
        PrintPerm(perm, n, ++permNum);
    } while (NextPerm(perm, n) == NOT_DONE);

    exit(0);
}    /* main */

/* eof */
--
______________________________________________________________________________
mike gleason                 [e-mail]             NCEMRSoft, baby!